package math;

import org.junit.Test;

/**
 * @Description 剑指 Offer 66. 构建乘积数组
 * @Author Firenut
 * @Date 2023-03-25 15:09
 */
public class T66_constructArr {
    // 可以看成一个n*n的二维数组,每个元素对应i位置的元素值看成1,
    // 实际求b[i]就是求不包含该元素的上三角元素乘积和下三角元素的乘积
    // 时间复杂度: O(n) 空间复杂度: O(1)
    public int[] constructArr(int[] a) {
        if (a.length == 0) {
            return new int[0];
        }
        int b[] = new int[a.length];
        b[0] = 1;
        // 求下三角
        for (int i = 1; i < b.length; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }

        int temp = 1;
        // 求上三角
        for (int i = b.length - 2; i >= 0; i--) {
            temp *= a[i + 1];
            b[i] *= temp;
        }
        return b;
    }

    // 两个for循环可以简化成一个
    public int[] constructArr1(int[] a) {
        if (a.length == 0) {
            return new int[0];
        }
        int b[] = new int[a.length];
        for (int i = 0; i < b.length; i++) {
            b[i] = 1;
        }
        int left = 1, right = 1;
        for (int i = 0; i < b.length; i++) {
            b[i] *= left;
            left *= a[i];
            b[b.length - 1 - i] *= right;
            right *= a[b.length - 1 - i];
        }
        return b;
    }
}